package leetCode.thirdWeek.stack;

import java.util.Stack;

public class Code_84 {
    public int[] heightsCopy;

    public int largestRectangleArea(int[] heights) {
        heightsCopy = heights;
        int MAX = 0;

        for (int i = 0; i < heights.length; i++) {
            int[] tmp = findLeftAndRight(i);
            if (calArea(tmp[0], tmp[1]) > MAX) {
                MAX = calArea(tmp[0], tmp[1]);
            }
        }

        return MAX;
    }

    public int[] findLeftAndRight(int i) {
        int pStart = i;
        int pEnd = i;
        while (pStart >= 0 && heightsCopy[pStart] >= heightsCopy[i]) pStart--;
        while (pEnd < heightsCopy.length && heightsCopy[pEnd] >= heightsCopy[i]) pEnd++;
        return new int[]{pStart, pEnd};
    }

    public int calArea(int i, int j) {//包含i，包含j
        if (i >= j) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int k = i + 1; k <= j - 1; k++) {
            if (heightsCopy[k] < min) min = heightsCopy[k];
        }
        return min * (j - i - 1);
    }
}
